/*-------------------------------------------------------------------------
 *
 * nodeMemoize.c
 *	  处理来自参数化节点的结果缓存的例程
 *
 * Portions Copyright (c) 2021-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 *
 * IDENTIFICATION
 *	  src/backend/executor/nodeMemoize.c
 *
 * Memoize节点旨在位于计划树中的参数化节点之上，以缓存来自它们的结果。其意图是，当一个参数值
 * 被节点看到后，重复扫描可以从缓存中获取元组，而不是必须重新扫描内部节点。查询规划器可能会选择
 * 在它认为先前看到的值的续扫描足够可能以合理化增加额外节点时，利用其中一个。
 *
 * 我们使用的缓存方法是哈希表。当缓存填满时，我们从不将元组溢出到磁盘，而是选择驱逐缓存中最近最少使用的条目。
 * 我们通过始终将新条目和我们寻找的条目推入双向链表的尾部来记住最近最少使用的条目。这意味着较旧的项
 * 始终会浮到LRU列表的顶部。
 *
 * 有时我们的调用者不会完成他们的扫描。例如，半连接仅需要运行直到找到匹配的元组，一旦找到，连接操作符将跳至
 * 下一个外部元组，而不会在该扫描中再次执行内部部分。因为这样，我们必须跟踪缓存条目何时完成，默认情况下，
 * 我们知道当扫描中没有可读取的元组时，它是完成的。然而，有些情况下我们可以在不耗尽全部元组扫描的情况下
 * 将缓存条目标记为完成。一个情况是唯一连接，其中连接操作员知道任何给定外部元组最多只有一个匹配。为了支持
 * 这样的情况，我们允许为缓存设置“singlerow”选项。此选项标记缓存条目为完成，在我们从子节点读取第一个元组后。
 *
 * 当我们为给定参数集填充缓存时，可能无法释放足够的内存来存储更多的元组。如果发生这种情况，则我们已
 * 经驱逐了所有其他缓存条目。当缓存另一个元组将导致我们超过内存预算时，我们必须释放正在填充的条目，并
 * 将状态机移动到MEMO_CACHE_BYPASS_MODE。这意味着我们将不再尝试缓存此特定扫描的进一步元组。我们没有
 * 足够的内存。状态机将在下次重新扫描时重置。如果缓存下一个参数的元组的内存要求较低，则可能会允许我们
 * 重新将有用条目放回缓存。
 *
 * INTERFACE ROUTINES
 *		ExecMemoize			- 查找缓存，未找到时执行子计划
 *		ExecInitMemoize		- 初始化节点和子节点
 *		ExecEndMemoize		- 关闭节点和子节点
 *		ExecReScanMemoize	- 重新扫描memoize节点
 *
 *		ExecMemoizeEstimate		估计平行计划所需的DSM空间
 *		ExecMemoizeInitializeDSM 初始化平行计划的DSM
 *		ExecMemoizeInitializeWorker 附加到平行工作中的DSM信息
 *		ExecMemoizeRetrieveInstrumentation 从工作中获取仪器
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "common/hashfn.h"
#include "executor/executor.h"
#include "executor/nodeMemoize.h"
#include "lib/ilist.h"
#include "miscadmin.h"
#include "utils/datum.h"
#include "utils/lsyscache.h"

/* ExecMemoize 状态机的状态 */
#define MEMO_CACHE_LOOKUP			1	/* 尝试执行缓存查找 */
#define MEMO_CACHE_FETCH_NEXT_TUPLE	2	/* 从缓存中获取另一个元组 */
#define MEMO_FILLING_CACHE			3	/* 读取外部节点以填充缓存 */
#define MEMO_CACHE_BYPASS_MODE		4	/* 绕过模式。只需从我们的
										 * 子计划中读取，而不缓存任何内容 */
#define MEMO_END_OF_SCAN			5	/* 准备重新扫描 */


/* 内存管理的辅助宏 */
#define EMPTY_ENTRY_MEMORY_BYTES(e)		(sizeof(MemoizeEntry) + \
										 sizeof(MemoizeKey) + \
										 (e)->key->params->t_len);
#define CACHE_TUPLE_BYTES(t)			(sizeof(MemoizeTuple) + \
										 (t)->mintuple->t_len)

 /* MemoizeTuple 存储单独缓存的元组 */
typedef struct MemoizeTuple
{
	MinimalTuple mintuple;		/* 缓存的元组 */
	struct MemoizeTuple *next;	/* 下一个具有相同参数
								 * 值的元组，或 NULL 如果这是最后一个 */
} MemoizeTuple;

/*
 * MemoizeKey
 * 缓存条目的哈希表键加上 LRU 列表链接
 */
typedef struct MemoizeKey
{
	MinimalTuple params;
	dlist_node	lru_node;		/* 指向 LRU 列表中下一个/上一个键的指针 */
} MemoizeKey;

/*
 * MemoizeEntry
 *		缓存哈希表存储的数据结构
 */
typedef struct MemoizeEntry
{
	MemoizeKey *key;			/* 哈希表查找的哈希键 */
	MemoizeTuple *tuplehead;	/* 指向第一个元组的指针，如果没有
								 * 为此条目缓存的元组则为 NULL */
	uint32		hash;			/* 哈希值（缓存） */
	char		status;			/* 哈希状态 */
	bool		complete;		/* 我们是否已完成读取外部计划？ */
} MemoizeEntry;


#define SH_PREFIX memoize
#define SH_ELEMENT_TYPE MemoizeEntry
#define SH_KEY_TYPE MemoizeKey *
#define SH_SCOPE static inline
#define SH_DECLARE
#include "lib/simplehash.h"

static uint32 fc_MemoizeHash_hash(struct memoize_hash *fc_tb,
							   const MemoizeKey *fc_key);
static bool fc_MemoizeHash_equal(struct memoize_hash *fc_tb,
							  const MemoizeKey *fc_params1,
							  const MemoizeKey *fc_params2);

#define SH_PREFIX memoize
#define SH_ELEMENT_TYPE MemoizeEntry
#define SH_KEY_TYPE MemoizeKey *
#define SH_KEY key
#define SH_HASH_KEY(tb, key) fc_MemoizeHash_hash(tb, key)
#define SH_EQUAL(tb, a, b) fc_MemoizeHash_equal(tb, a, b)
#define SH_SCOPE static inline
#define SH_STORE_HASH
#define SH_GET_HASH(tb, a) a->hash
#define SH_DEFINE
#include "lib/simplehash.h"

/*
 * MemoizeHash_hash
 *		简单哈希哈希表的哈希函数。这里不使用'key'，因为我们
 *		要求所有表查找首先用要查找的键值填充MemoizeState的
 *		probeslot。
 */
static uint32 fc_MemoizeHash_hash(struct memoize_hash *fc_tb, const MemoizeKey *fc_key)
{
	MemoizeState *fc_mstate = (MemoizeState *) fc_tb->private_data;
	ExprContext *fc_econtext = fc_mstate->ss.ps.ps_ExprContext;
	MemoryContext fc_oldcontext;
	TupleTableSlot *fc_pslot = fc_mstate->probeslot;
	uint32		fc_hashkey = 0;
	int			fc_numkeys = fc_mstate->nkeys;

	fc_oldcontext = MemoryContextSwitchTo(fc_econtext->ecxt_per_tuple_memory);

	if (fc_mstate->binary_mode)
	{
		for (int fc_i = 0; fc_i < fc_numkeys; fc_i++)
		{
			/* 通过旋转组合连续的哈希键 */
			fc_hashkey = pg_rotate_left32(fc_hashkey, 1);

			if (!fc_pslot->tts_isnull[fc_i])	/* 将 null 视为哈希键 0 */
			{
				FormData_pg_attribute *fc_attr;
				uint32		fc_hkey;

				fc_attr = &fc_pslot->tts_tupleDescriptor->attrs[fc_i];

				fc_hkey = datum_image_hash(fc_pslot->tts_values[fc_i], fc_attr->attbyval, fc_attr->attlen);

				fc_hashkey ^= fc_hkey;
			}
		}
	}
	else
	{
		FmgrInfo   *fc_hashfunctions = fc_mstate->hashfunctions;
		Oid		   *fc_collations = fc_mstate->collations;

		for (int fc_i = 0; fc_i < fc_numkeys; fc_i++)
		{
			/* 通过旋转组合连续的哈希键 */
			fc_hashkey = pg_rotate_left32(fc_hashkey, 1);

			if (!fc_pslot->tts_isnull[fc_i])	/* 将 null 视为哈希键 0 */
			{
				uint32		fc_hkey;

				fc_hkey = DatumGetUInt32(FunctionCall1Coll(&fc_hashfunctions[fc_i],
														fc_collations[fc_i], fc_pslot->tts_values[fc_i]));
				fc_hashkey ^= fc_hkey;
			}
		}
	}

	MemoryContextSwitchTo(fc_oldcontext);
	return murmurhash32(fc_hashkey);
}

/*
 * MemoizeHash_equal
 *		在哈希表查找期间确认哈希值匹配的相等性函数。'key2'从未使用。
 *		相反，MemoizeState的probeslot始终填充有关正在查找的内容的详细信息。
 */
static bool fc_MemoizeHash_equal(struct memoize_hash *fc_tb, const MemoizeKey *fc_key1,
				  const MemoizeKey *fc_key2)
{
	MemoizeState *fc_mstate = (MemoizeState *) fc_tb->private_data;
	ExprContext *fc_econtext = fc_mstate->ss.ps.ps_ExprContext;
	TupleTableSlot *fc_tslot = fc_mstate->tableslot;
	TupleTableSlot *fc_pslot = fc_mstate->probeslot;

	/* probeslot应该已由prepare_probe_slot()准备好 */
	ExecStoreMinimalTuple(fc_key1->params, fc_tslot, false);

	if (fc_mstate->binary_mode)
	{
		MemoryContext fc_oldcontext;
		int			fc_numkeys = fc_mstate->nkeys;
		bool		fc_match = true;

		fc_oldcontext = MemoryContextSwitchTo(fc_econtext->ecxt_per_tuple_memory);

		slot_getallattrs(fc_tslot);
		slot_getallattrs(fc_pslot);

		for (int fc_i = 0; fc_i < fc_numkeys; fc_i++)
		{
			FormData_pg_attribute *fc_attr;

			if (fc_tslot->tts_isnull[fc_i] != fc_pslot->tts_isnull[fc_i])
			{
				fc_match = false;
				break;
			}

			/* 都是NULL？它们相等 */
			if (fc_tslot->tts_isnull[fc_i])
				continue;

			/* 对这两个数据项进行二进制比较 */
			fc_attr = &fc_tslot->tts_tupleDescriptor->attrs[fc_i];
			if (!datum_image_eq(fc_tslot->tts_values[fc_i], fc_pslot->tts_values[fc_i],
								fc_attr->attbyval, fc_attr->attlen))
			{
				fc_match = false;
				break;
			}
		}

		MemoryContextSwitchTo(fc_oldcontext);
		return fc_match;
	}
	else
	{
		fc_econtext->ecxt_innertuple = fc_tslot;
		fc_econtext->ecxt_outertuple = fc_pslot;
		return ExecQual(fc_mstate->cache_eq_expr, fc_econtext);
	}
}

/*
 * 初始化哈希表为空。
 */
static void fc_build_hash_table(MemoizeState *fc_mstate, uint32 fc_size)
{
	/* 当没有给出有效大小时，猜测一个合适的大小。 */
	if (fc_size == 0)
		fc_size = 1024;

	/* memoize_create会将大小转换为2的幂 */
	fc_mstate->hashtable = memoize_create(fc_mstate->tableContext, fc_size, fc_mstate);
}

/*
 * prepare_probe_slot
 *		用存储在'key'中的元组的值填充mstate的probeslot。
 *		如果'key'为NULL，则通过评估mstate的param_exprs来进行填充。
 */
static inline void fc_prepare_probe_slot(MemoizeState *fc_mstate, MemoizeKey *fc_key)
{
	TupleTableSlot *fc_pslot = fc_mstate->probeslot;
	TupleTableSlot *fc_tslot = fc_mstate->tableslot;
	int			fc_numKeys = fc_mstate->nkeys;

	ExecClearTuple(fc_pslot);

	if (fc_key == NULL)
	{
		ExprContext *fc_econtext = fc_mstate->ss.ps.ps_ExprContext;
		MemoryContext fc_oldcontext;

		fc_oldcontext = MemoryContextSwitchTo(fc_econtext->ecxt_per_tuple_memory);

		/* 根据当前参数值设置probeslot的值 */
		for (int fc_i = 0; fc_i < fc_numKeys; fc_i++)
			fc_pslot->tts_values[fc_i] = ExecEvalExpr(fc_mstate->param_exprs[fc_i],
												fc_econtext,
												&fc_pslot->tts_isnull[fc_i]);

		MemoryContextSwitchTo(fc_oldcontext);
	}
	else
	{
		/* 处理键的MinimalTuple并将值存储在probeslot中 */
		ExecStoreMinimalTuple(fc_key->params, fc_tslot, false);
		slot_getallattrs(fc_tslot);
		memcpy(fc_pslot->tts_values, fc_tslot->tts_values, sizeof(Datum) * fc_numKeys);
		memcpy(fc_pslot->tts_isnull, fc_tslot->tts_isnull, sizeof(bool) * fc_numKeys);
	}

	ExecStoreVirtualTuple(fc_pslot);
}

/*
 * entry_purge_tuples
 *		从'entry'指向的缓存条目中移除所有元组。这
 *		留下一个空的缓存条目。此外，更新内存管理以
 *		反映元组的移除。
 */
static inline void fc_entry_purge_tuples(MemoizeState *fc_mstate, MemoizeEntry *fc_entry)
{
	MemoizeTuple *fc_tuple = fc_entry->tuplehead;
	uint64		fc_freed_mem = 0;

	while (fc_tuple != NULL)
	{
		MemoizeTuple *fc_next = fc_tuple->next;

		fc_freed_mem += CACHE_TUPLE_BYTES(fc_tuple);

		/* 释放用于该元组的内存 */
		pfree(fc_tuple->mintuple);
		pfree(fc_tuple);

		fc_tuple = fc_next;
	}

	fc_entry->complete = false;
	fc_entry->tuplehead = NULL;

	/* 更新内存管理 */
	fc_mstate->mem_used -= fc_freed_mem;
}

/*
 * remove_cache_entry
 *		从缓存中移除'entry'并释放其使用的内存。
 */
static void fc_remove_cache_entry(MemoizeState *fc_mstate, MemoizeEntry *fc_entry)
{
	MemoizeKey *fc_key = fc_entry->key;

	dlist_delete(&fc_entry->key->lru_node);

	/* 从该条目中移除所有元组 */
	fc_entry_purge_tuples(fc_mstate, fc_entry);

	/*
	 * 更新内存管理。entry_purge_tuples应该已经
	 * 减去每个缓存元组使用的内存。在这里我们只更新
	 * 条目本身使用的数量。
	 */
	fc_mstate->mem_used -= EMPTY_ENTRY_MEMORY_BYTES(fc_entry);

	/* 从缓存中移除条目 */
	memoize_delete_item(fc_mstate->hashtable, fc_entry);

	pfree(fc_key->params);
	pfree(fc_key);
}

/*
 * cache_purge_all
 *		从缓存中移除所有项目
 */
static void fc_cache_purge_all(MemoizeState *fc_mstate)
{
	uint64		fc_evictions = fc_mstate->hashtable->members;
	PlanState  *fc_pstate = (PlanState *) fc_mstate;

	/*
	 * 移除所有项目的最有效方法可能是重置
	 * 缓存的内存上下文，然后重建一个新的哈希表。
	 * 这节省了逐个移除每个项目并释放每个缓存元组的时间
	 */
	MemoryContextReset(fc_mstate->tableContext);

	/* 使哈希表与原始大小相同 */
	fc_build_hash_table(fc_mstate, ((Memoize *) fc_pstate->plan)->est_entries);

	/* 重置LRU列表 */
	dlist_init(&fc_mstate->lru_list);
	fc_mstate->last_tuple = NULL;
	fc_mstate->entry = NULL;

	fc_mstate->mem_used = 0;

	/* XXX 我们是否应该添加一些新内容来跟踪这些清除？ */
	fc_mstate->stats.cache_evictions += fc_evictions; /* 更新统计信息 */
}

/*
 * cache_reduce_memory
 *		从缓存中驱逐较旧和最近使用较少的项目，以
 *		减少内存消耗，使其回到小于
 *		MemoizeState的mem_limit。
 *
 * 如果'specialkey'不为NULL，则在键所属于的条目
 * 从缓存中移除时，会导致函数返回false。
 */
static bool fc_cache_reduce_memory(MemoizeState *fc_mstate, MemoizeKey *fc_specialkey)
{
	bool		fc_specialkey_intact = true;	/* 目前为止 */
	dlist_mutable_iter fc_iter;
	uint64		fc_evictions = 0;

	/* 更新峰值内存使用情况 */
	if (fc_mstate->mem_used > fc_mstate->stats.mem_peak)
		fc_mstate->stats.mem_peak = fc_mstate->mem_used;

	/* 我们预计只有在超出内存预算时才会被调用 */
	Assert(fc_mstate->mem_used > fc_mstate->mem_limit);

	/* 从 LRU 列表的开头开始驱逐过程。 */
	dlist_foreach_modify(fc_iter, &fc_mstate->lru_list)
	{
		MemoizeKey *fc_key = dlist_container(MemoizeKey, lru_node, fc_iter.cur);
		MemoizeEntry *fc_entry;

		/*
		 * 准备哈希探测槽，以便查找此 LRU 
		 * 条目。 
		 */
		fc_prepare_probe_slot(fc_mstate, fc_key);

		/*
		 * 理想情况下，LRU 列表指针应存储在条目本身 
		 * 中，而不是在键中。不幸的是，我们无法这样做，因为 
		 * simplehash.h 代码可能会调整表的大小并为 
		 * 条目分配新内存，这会导致这些指针指向旧 
		 * 的桶。然而，使用键来存储这是可以的，因为它仅 
		 * 通过条目中的一个指针引用，当然无论何时哈希 
		 * 表调整大小，它都会跟随条目。由于我们这里只有一个 
		 * 指向键的指针，因此我们必须执行哈希表查找来 
		 * 查找该键所属的条目。 
		 */
		fc_entry = memoize_lookup(fc_mstate->hashtable, NULL);

		/*
		 * 进行基本检查，以确保我们找到了属于 LRU 列表 
		 * 项目的条目。一个不当行为的哈希或等式函数可能会 
		 * 导致找不到条目或找到错误的条目。 
		 */
		if (unlikely(fc_entry == NULL || fc_entry->key != fc_key))
			elog(ERROR, "could not find memoization table entry");

		/*
		 * 如果我们在缓存被填充新元组时被调用以释放内存， 
		 * 那么我们最好小心，因为我们可能会最终释放 
		 * 'specialkey' 所属的条目。通常，调用者将 
		 * 'specialkey' 作为当前正在填充的缓存 
		 * 条目的键传递，因此我们必须将 
		 * 'specialkey_intact' 设置为 false，以通知调用者 
		 * specialkey 条目已被移除。 
		 */
		if (fc_key == fc_specialkey)
			fc_specialkey_intact = false;

		/*
		 * 最后移除条目。这将从 LRU 列表中移除。 
		 */
		fc_remove_cache_entry(fc_mstate, fc_entry);

		fc_evictions++;

		/* 如果我们释放了足够的内存，则退出 */
		if (fc_mstate->mem_used <= fc_mstate->mem_limit)
			break;
	}

	fc_mstate->stats.cache_evictions += fc_evictions; /* 更新统计信息 */

	return fc_specialkey_intact;
}

/*
 * cache_lookup
 *		执行查找以查看我们是否已经根据 
 *		扫描的当前参数缓存了元组。如果找到现有条目， 
 *		我们将其移动到 LRU 列表的末尾，设置 *found 为 
 *		true，然后返回。如果未找到条目，则 
 *		创建一个新条目并将其添加到 LRU 列表的末尾。 
 *		我们还将更新缓存内存核算，并在超出内存 
 *		预算时移除较旧的条目。如果我们成功释放了足够的 
 *		内存，则返回新条目，否则返回 NULL。
 *
 * 调用者可以假设当 *found 为 true 时，我们永远不会返回 NULL。
 */
static MemoizeEntry *
fc_cache_lookup(MemoizeState *fc_mstate, bool *fc_found)
{
	MemoizeKey *fc_key;
	MemoizeEntry *fc_entry;
	MemoryContext fc_oldcontext;

	/* 用当前扫描参数准备探测槽 */
	fc_prepare_probe_slot(fc_mstate, NULL);

	/*
	 * 将新条目添加到缓存中。无需传递有效的键，因为 
	 * 哈希函数使用 mstate 的 probeslot，我们在上面填充过。
	 */
	fc_entry = memoize_insert(fc_mstate->hashtable, NULL, fc_found);

	if (*fc_found)
	{
		/*
		 * 将现有条目移至 LRU 列表的尾部，以将其标记为 
		 * 最近使用的项目。 
		 */
		dlist_move_tail(&fc_mstate->lru_list, &fc_entry->key->lru_node);

		return fc_entry;
	}

	fc_oldcontext = MemoryContextSwitchTo(fc_mstate->tableContext);

	/* 分配一个新键 */
	fc_entry->key = fc_key = (MemoizeKey *) palloc(sizeof(MemoizeKey));
	fc_key->params = ExecCopySlotMinimalTuple(fc_mstate->probeslot);

	/* 更新总缓存内存利用率 */
	fc_mstate->mem_used += EMPTY_ENTRY_MEMORY_BYTES(fc_entry);

	/* 初始化此条目 */
	fc_entry->complete = false;
	fc_entry->tuplehead = NULL;

	/*
	 * 由于这是最近使用的条目，将该条目推送到 
	 * LRU 列表的末尾。 
	 */
	dlist_push_tail(&fc_mstate->lru_list, &fc_entry->key->lru_node);

	fc_mstate->last_tuple = NULL;

	MemoryContextSwitchTo(fc_oldcontext);

	/*
	 * 如果我们超出了内存预算，那么我们将腾出一些空间 
	 * 在缓存中。 
	 */
	if (fc_mstate->mem_used > fc_mstate->mem_limit)
	{
		/*
		 * 尝试释放一些内存。在这里我们不太可能失败， 
		 * 因为我们刚刚添加的条目尚未包含 
		 * 任何元组，并且我们能够移除任何其他条目以减少 
		 * 内存消耗。 
		 */
		if (unlikely(!fc_cache_reduce_memory(fc_mstate, fc_key)))
			return NULL;

		/*
		 * 从缓存中移除条目的过程可能导致 
		 * simplehash.h 中的代码将元素移到哈希表的较早 
		 * 桶中。如果是这样，我们需要通过执行查找来 
		 * 再次找到条目。幸运的是，我们可以通过检查 
		 * 条目是否仍在使用，以及键指针是否与 
		 * 我们预期的键匹配，从而检测到这是否发生。
		 */
		if (fc_entry->status != memoize_SH_IN_USE || fc_entry->key != fc_key)
		{
			/*
			 * 我们需要重新填充探测槽，因为在上述缓存 
			 * 驱逐过程中执行的查找将存储其他键。 
			 */
			fc_prepare_probe_slot(fc_mstate, fc_key);

			/* 重新找到新添加的条目 */
			fc_entry = memoize_lookup(fc_mstate->hashtable, NULL);
			Assert(fc_entry != NULL);
		}
	}

	return fc_entry;
}

/*
 * cache_store_tuple
 *		将存储在 'slot' 中的元组添加到 mstate 当前的 
 *		缓存条目中。缓存条目必须已经通过 cache_lookup() 
 *		进行过创建。mstate 的 last_tuple 字段必须指向 
 *		mstate->entry 的元组列表的尾部。
 */
static bool fc_cache_store_tuple(MemoizeState *fc_mstate, TupleTableSlot *fc_slot)
{
	MemoizeTuple *fc_tuple;
	MemoizeEntry *fc_entry = fc_mstate->entry;
	MemoryContext fc_oldcontext;

	Assert(fc_slot != NULL);
	Assert(fc_entry != NULL);

	fc_oldcontext = MemoryContextSwitchTo(fc_mstate->tableContext);

	fc_tuple = (MemoizeTuple *) palloc(sizeof(MemoizeTuple));
	fc_tuple->mintuple = ExecCopySlotMinimalTuple(fc_slot);
	fc_tuple->next = NULL;

	/* 记录我们刚刚消耗的内存 */
	fc_mstate->mem_used += CACHE_TUPLE_BYTES(fc_tuple);

	if (fc_entry->tuplehead == NULL)
	{
		/*
		 * 这是该条目的第一个元组，因此只需将列表头 
		 * 指向它。 
		 */
		fc_entry->tuplehead = fc_tuple;
	}
	else
	{
		/* 将此元组推送到列表的尾部 */
		fc_mstate->last_tuple->next = fc_tuple;
	}

	fc_mstate->last_tuple = fc_tuple;
	MemoryContextSwitchTo(fc_oldcontext);

	/*
	 * 如果我们超出了内存预算，那么在缓存中腾出一些 
	 * 空间。 
	 */
	if (fc_mstate->mem_used > fc_mstate->mem_limit)
	{
		MemoizeKey *fc_key = fc_entry->key;

		if (!fc_cache_reduce_memory(fc_mstate, fc_key))
			return false;

		/*
		 * 从缓存中移除条目的过程可能导致 
		 * simplehash.h 中的代码将元素移到哈希表的较早 
		 * 桶中。如果是这样，我们需要通过执行查找来 
		 * 再次找到条目。幸运的是，我们可以通过检查 
		 * 条目是否仍在使用，以及键指针是否与 
		 * 我们预期的键匹配，从而检测到这是否发生。
		 */
		if (fc_entry->status != memoize_SH_IN_USE || fc_entry->key != fc_key)
		{
			/*
			 * 我们需要重新填充探测槽，因为在上述缓存 
			 * 驱逐过程中执行的查找将存储其他键。 
			 */
			fc_prepare_probe_slot(fc_mstate, fc_key);

			/* 重新找到条目 */
			fc_mstate->entry = fc_entry = memoize_lookup(fc_mstate->hashtable, NULL);
			Assert(fc_entry != NULL);
		}
	}

	return true;
}

static TupleTableSlot * fc_ExecMemoize(PlanState *fc_pstate)
{
	MemoizeState *fc_node = castNode(MemoizeState, fc_pstate);
	ExprContext *fc_econtext = fc_node->ss.ps.ps_ExprContext;
	PlanState  *fc_outerNode;
	TupleTableSlot *fc_slot;

	CHECK_FOR_INTERRUPTS();

	/*
	 * 重置每个元组的内存上下文，以释放在上一个元组周期中分配的任何表达式评估
	 * 存储。
	 */
	ResetExprContext(fc_econtext);

	switch (fc_node->mstatus)
	{
		case MEMO_CACHE_LOOKUP:
			{
				MemoizeEntry *fc_entry;
				TupleTableSlot *fc_outerslot;
				bool		fc_found;

				Assert(fc_node->entry == NULL);

				/*
				 * 我们仅在扫描的第一次调用时处于此状态。
				 * 在这里，我们查看是否之前已经看到 
				 * 当前参数，并且是否已经缓存了 
				 * 外部计划将为这些参数返回的完整记录集。
				 *
				 * 当我们找到有效的缓存条目时，我们将返回 
				 * 其中的第一个元组。如果未找到，我们将创建 
				 * 一个缓存条目，然后尝试从外部扫描中获取 
				 * 一个元组。如果在那里找到一个，我们将尝试 
				 * 将其缓存。
				 */

				
/* 查看我们是否为当前参数缓存了任何内容 */
				fc_entry = fc_cache_lookup(fc_node, &fc_found);

				if (fc_found && fc_entry->complete)
				{
					fc_node->stats.cache_hits += 1;	/* 统计信息更新 */

					/*
					 * 设置 last_tuple 和 entry，以便状态
					 * MEMO_CACHE_FETCH_NEXT_TUPLE 可以轻松找到这些参数的下一个
					 * 元组。
					 */
					fc_node->last_tuple = fc_entry->tuplehead;
					fc_node->entry = fc_entry;

					/* 获取第一个缓存的元组（如果存在的话） */
					if (fc_entry->tuplehead)
					{
						fc_node->mstatus = MEMO_CACHE_FETCH_NEXT_TUPLE;

						fc_slot = fc_node->ss.ps.ps_ResultTupleSlot;
						ExecStoreMinimalTuple(fc_entry->tuplehead->mintuple,
											  fc_slot, false);

						return fc_slot;
					}

					/* 缓存条目没有任何元组。 */
					fc_node->mstatus = MEMO_END_OF_SCAN;
					return NULL;
				}

				/* 处理缓存未命中 */
				fc_node->stats.cache_misses += 1;	/* 统计信息更新 */

				if (fc_found)
				{
					/* 
					 * 找到了缓存条目，但对该条目的扫描
					 * 并没有完成。我们将移除所有
					 * 元组并重新开始。继续上次未完成的地方可能会很诱人，
					 * 但是没有保证外部节点会以相同的顺序生成元组。
					 */
					fc_entry_purge_tuples(fc_node, fc_entry);
				}

				/* 扫描外部节点以获取要缓存的元组 */
				fc_outerNode = outerPlanState(fc_node);
				fc_outerslot = ExecProcNode(fc_outerNode);
				if (TupIsNull(fc_outerslot))
				{
					/* 
					 * cache_lookup 可能由于未能
					 * 释放足够的缓存空间而返回 NULL，因此确保我们在这里不做任何
					 * 假设它成功的事情。这里没有必要进入旁路模式，因为我们正在设置 mstatus 为扫描结束。
					 */
					if (likely(fc_entry))
						fc_entry->complete = true;

					fc_node->mstatus = MEMO_END_OF_SCAN;
					return NULL;
				}

				fc_node->entry = fc_entry;

				/* 
				 * 如果我们未能创建条目或未能将
				 * 元组存储在条目中，则进入旁路模式。
				 */
				if (unlikely(fc_entry == NULL ||
							 !fc_cache_store_tuple(fc_node, fc_outerslot)))
				{
					fc_node->stats.cache_overflows += 1;	/* 统计信息更新 */

					fc_node->mstatus = MEMO_CACHE_BYPASS_MODE;

					/* 
					 * 不需要清除 last_tuple，因为我们将在扫描结束之前保持在旁路模式。
					 */
				}
				else
				{
					/* 
					 * 如果我们只期望从此扫描中获得一行，则
					 * 可以标记我们不期望更多。这允许
					 * 缓存查找即使在扫描未执行完成时也能工作。
					 */
					fc_entry->complete = fc_node->singlerow;
					fc_node->mstatus = MEMO_FILLING_CACHE;
				}

				fc_slot = fc_node->ss.ps.ps_ResultTupleSlot;
				ExecCopySlot(fc_slot, fc_outerslot);
				return fc_slot;
			}

		case MEMO_CACHE_FETCH_NEXT_TUPLE:
			{
				/* 我们不应该处于这个状态，如果这些未设置 */
				Assert(fc_node->entry != NULL);
				Assert(fc_node->last_tuple != NULL);

				/* 跳过下一个元组以输出 */
				fc_node->last_tuple = fc_node->last_tuple->next;

				/* 缓存中没有更多元组 */
				if (fc_node->last_tuple == NULL)
				{
					fc_node->mstatus = MEMO_END_OF_SCAN;
					return NULL;
				}

				fc_slot = fc_node->ss.ps.ps_ResultTupleSlot;
				ExecStoreMinimalTuple(fc_node->last_tuple->mintuple, fc_slot,
									  false);

				return fc_slot;
			}

		case MEMO_FILLING_CACHE:
			{
				TupleTableSlot *fc_outerslot;
				MemoizeEntry *fc_entry = fc_node->entry;

				/* 条目应该已经由 MEMO_CACHE_LOOKUP 设置 */
				Assert(fc_entry != NULL);

				/* 
				 * 当处于 MEMO_FILLING_CACHE 状态时，我们刚刚出现了
				 * 缓存未命中的情况，并正在用当前
				 * 扫描的元组填充缓存。
				 */
				fc_outerNode = outerPlanState(fc_node);
				fc_outerslot = ExecProcNode(fc_outerNode);
				if (TupIsNull(fc_outerslot))
				{
					/* 没有更多元组。将其标记为完成 */
					fc_entry->complete = true;
					fc_node->mstatus = MEMO_END_OF_SCAN;
					return NULL;
				}

				/* 
				 * 验证规划者是否正确设置了 singlerow 标志。它
				 * 应该只有在每个缓存条目最多返回 1 行时才设置该标志。
				 */
				if (unlikely(fc_entry->complete))
					elog(ERROR, "cache entry already complete");

				/* 在当前缓存条目中记录元组 */
				if (unlikely(!fc_cache_store_tuple(fc_node, fc_outerslot)))
				{
					/* 不能存储吗？处理溢出 */
					fc_node->stats.cache_overflows += 1;	/* 统计信息更新 */

					fc_node->mstatus = MEMO_CACHE_BYPASS_MODE;

					/* 
					 * 不需要清除条目或 last_tuple，因为我们将在扫描结束之前保持在旁路模式。
					 */
				}

				fc_slot = fc_node->ss.ps.ps_ResultTupleSlot;
				ExecCopySlot(fc_slot, fc_outerslot);
				return fc_slot;
			}

		case MEMO_CACHE_BYPASS_MODE:
			{
				TupleTableSlot *fc_outerslot;

				/* 
				 * 当处于旁路模式时，我们继续读取元组而不
				 * 进行缓存。我们需要等到下一次重新扫描才能
				 * 退出此模式。
				 */
				fc_outerNode = outerPlanState(fc_node);
				fc_outerslot = ExecProcNode(fc_outerNode);
				if (TupIsNull(fc_outerslot))
				{
					fc_node->mstatus = MEMO_END_OF_SCAN;
					return NULL;
				}

				fc_slot = fc_node->ss.ps.ps_ResultTupleSlot;
				ExecCopySlot(fc_slot, fc_outerslot);
				return fc_slot;
			}

		case MEMO_END_OF_SCAN:

			/* 
			 * 我们已经为此扫描返回了 NULL，但以防
			 * 有人错误地再次调用我们。
			 */
			return NULL;

		default:
			elog(ERROR, "unrecognized memoize state: %d",
				 (int) fc_node->mstatus);
			return NULL;
	}							/* switch */
}

MemoizeState *
ExecInitMemoize(Memoize *fc_node, EState *fc_estate, int fc_eflags)
{
	MemoizeState *fc_mstate = makeNode(MemoizeState);
	Plan	   *fc_outerNode;
	int			fc_i;
	int			fc_nkeys;
	Oid		   *fc_eqfuncoids;

	/* 检查不支持的标志 */
	Assert(!(fc_eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));

	fc_mstate->ss.ps.plan = (Plan *) fc_node;
	fc_mstate->ss.ps.state = fc_estate;
	fc_mstate->ss.ps.ExecProcNode = fc_ExecMemoize;

	/*
	 * 杂项初始化
	 *
	 * 为节点创建表达式上下文
	 */
	ExecAssignExprContext(fc_estate, &fc_mstate->ss.ps);

	fc_outerNode = outerPlan(fc_node);
	outerPlanState(fc_mstate) = ExecInitNode(fc_outerNode, fc_estate, fc_eflags);

	/* 
	 * 初始化返回插槽和类型。无需初始化投影信息
	 * 因为此节点不执行投影。
	 */
	ExecInitResultTupleSlotTL(&fc_mstate->ss.ps, &TTSOpsMinimalTuple);
	fc_mstate->ss.ps.ps_ProjInfo = NULL;

	/*
	 * 初始化扫描槽和类型。
	 */
	ExecCreateScanSlotFromOuterPlan(fc_estate, &fc_mstate->ss, &TTSOpsMinimalTuple);

	/* 
	 * 将状态机设置为查找缓存。我们不会找到任何东西
	 * 直到我们缓存一些东西，但这保存了一个特殊情况来创建
	 * 第一个条目。
	 */
	fc_mstate->mstatus = MEMO_CACHE_LOOKUP;

	fc_mstate->nkeys = fc_nkeys = fc_node->numKeys;
	fc_mstate->hashkeydesc = ExecTypeFromExprList(fc_node->param_exprs);
	fc_mstate->tableslot = MakeSingleTupleTableSlot(fc_mstate->hashkeydesc,
												 &TTSOpsMinimalTuple);
	fc_mstate->probeslot = MakeSingleTupleTableSlot(fc_mstate->hashkeydesc,
												 &TTSOpsVirtual);

	fc_mstate->param_exprs = (ExprState **) palloc(fc_nkeys * sizeof(ExprState *));
	fc_mstate->collations = fc_node->collations;	/* 直接指向计划
											 * 数据 */
	fc_mstate->hashfunctions = (FmgrInfo *) palloc(fc_nkeys * sizeof(FmgrInfo));

	fc_eqfuncoids = palloc(fc_nkeys * sizeof(Oid));

	for (fc_i = 0; fc_i < fc_nkeys; fc_i++)
	{
		Oid			fc_hashop = fc_node->hashOperators[fc_i];
		Oid			fc_left_hashfn;
		Oid			fc_right_hashfn;
		Expr	   *fc_param_expr = (Expr *) list_nth(fc_node->param_exprs, fc_i);

		if (!get_op_hash_functions(fc_hashop, &fc_left_hashfn, &fc_right_hashfn))
			elog(ERROR, "could not find hash function for hash operator %u",
				 fc_hashop);

		fmgr_info(fc_left_hashfn, &fc_mstate->hashfunctions[fc_i]);

		fc_mstate->param_exprs[fc_i] = ExecInitExpr(fc_param_expr, (PlanState *) fc_mstate);
		fc_eqfuncoids[fc_i] = get_opcode(fc_hashop);
	}

	fc_mstate->cache_eq_expr = ExecBuildParamSetEqual(fc_mstate->hashkeydesc,
												   &TTSOpsMinimalTuple,
												   &TTSOpsVirtual,
												   fc_eqfuncoids,
												   fc_node->collations,
												   fc_node->param_exprs,
												   (PlanState *) fc_mstate);

	pfree(fc_eqfuncoids);
	fc_mstate->mem_used = 0;

	/* 限制缓存使用的总内存为此 */
	fc_mstate->mem_limit = get_hash_memory_limit();

	/* 专门用于缓存的内存上下文 */
	fc_mstate->tableContext = AllocSetContextCreate(CurrentMemoryContext,
												 "MemoizeHashTable",
												 ALLOCSET_DEFAULT_SIZES);

	dlist_init(&fc_mstate->lru_list);
	fc_mstate->last_tuple = NULL;
	fc_mstate->entry = NULL;

	/* 
	 * 标记在获取第一个记录后我们是否可以假设缓存条目已完成。
	 * 一些调用者在获取第一个匹配后可能不会再次调用我们。
	 * 例如，执行唯一连接的连接操作符能够在获取第一个匹配的内部元组后跳过下一个外部元组。
	 * 在这种情况下，获取第一个元组后缓存条目即已完成。
	 * 这允许我们将其标记为已完成。
	 */
	fc_mstate->singlerow = fc_node->singlerow;
	fc_mstate->keyparamids = fc_node->keyparamids;

	/* 
	 * 记录缓存键是否应逐位比较，或使用类型的哈希相等运算符进行逻辑比较
	 */
	fc_mstate->binary_mode = fc_node->binary_mode;

	/* 清零统计计数器 */
	memset(&fc_mstate->stats, 0, sizeof(MemoizeInstrumentation));

	/* 分配并设置实际缓存 */
	fc_build_hash_table(fc_mstate, fc_node->est_entries);

	return fc_mstate;
}

void ExecEndMemoize(MemoizeState *fc_node)
{
#ifdef USE_ASSERT_CHECKING
	/* 验证内存计费代码在断言构建中是否正确。*/
	{
		int			fc_count;
		uint64		fc_mem = 0;
		memoize_iterator fc_i;
		MemoizeEntry *fc_entry;

		memoize_start_iterate(fc_node->hashtable, &fc_i);

		fc_count = 0;
		while ((fc_entry = memoize_iterate(fc_node->hashtable, &fc_i)) != NULL)
		{
			MemoizeTuple *fc_tuple = fc_entry->tuplehead;

			fc_mem += EMPTY_ENTRY_MEMORY_BYTES(fc_entry);
			while (fc_tuple != NULL)
			{
				fc_mem += CACHE_TUPLE_BYTES(fc_tuple);
				fc_tuple = fc_tuple->next;
			}
			fc_count++;
		}

		Assert(fc_count == fc_node->hashtable->members);
		Assert(fc_mem == fc_node->mem_used);
	}
#endif

	/*
	 * 当结束一个并行工作者时，将工作者收集到的统计信息
	 * 复制回共享内存，以便主进程可以在 EXPLAIN ANALYZE 中报告。
	 */
	if (fc_node->shared_info != NULL && IsParallelWorker())
	{
		MemoizeInstrumentation *fc_si;

		/* 使 mem_peak 在 EXPLAIN 中可用 */
		if (fc_node->stats.mem_peak == 0)
			fc_node->stats.mem_peak = fc_node->mem_used;

		Assert(ParallelWorkerNumber <= fc_node->shared_info->num_workers);
		fc_si = &fc_node->shared_info->sinstrument[ParallelWorkerNumber];
		memcpy(fc_si, &fc_node->stats, sizeof(MemoizeInstrumentation));
	}

	/* 移除缓存上下文 */
	MemoryContextDelete(fc_node->tableContext);

	ExecClearTuple(fc_node->ss.ss_ScanTupleSlot);
	/* 必须删除指向缓存结果元组的指针 */
	ExecClearTuple(fc_node->ss.ps.ps_ResultTupleSlot);

	/*
	 * 释放 exprcontext
	 */
	ExecFreeExprContext(&fc_node->ss.ps);

	/*
	 * 关闭子计划
	 */
	ExecEndNode(outerPlanState(fc_node));
}

void ExecReScanMemoize(MemoizeState *fc_node)
{
	PlanState  *fc_outerPlan = outerPlanState(fc_node);

	/* 标记我们必须为一组新参数查找缓存 */
	fc_node->mstatus = MEMO_CACHE_LOOKUP;

	/* 使最后一次扫描使用的指针无效 */
	fc_node->entry = NULL;
	fc_node->last_tuple = NULL;

	/*
	 * 如果子节点的chgParam不为空，则计划将由第一个ExecProcNode重新扫描。
	 */
	if (fc_outerPlan->chgParam == NULL)
		ExecReScan(fc_outerPlan);

	/*
	 * 如果更改的参数不在缓存键中，则清除整个缓存。
	 */
	if (bms_nonempty_difference(fc_outerPlan->chgParam, fc_node->keyparamids))
		fc_cache_purge_all(fc_node);
}

/*
 * ExecEstimateCacheEntryOverheadBytes
 *		供查询规划器使用，以帮助估算存储
 *		缓存中单个条目所需的内存量。
 */
double ExecEstimateCacheEntryOverheadBytes(double fc_ntuples)
{
	return sizeof(MemoizeEntry) + sizeof(MemoizeKey) + sizeof(MemoizeTuple) *
		fc_ntuples;
}

/* ----------------------------------------------------------------
 *						并行查询支持
 * ----------------------------------------------------------------
 */

 /* ----------------------------------------------------------------
  *		ExecMemoizeEstimate
  *
  *		估算传播备忘统计所需的空间。
  * ----------------------------------------------------------------
  */
void ExecMemoizeEstimate(MemoizeState *fc_node, ParallelContext *fc_pcxt)
{
	Size		fc_size;

	/* 如果没有工具监控或没有工作程序，则不需要此 */
	if (!fc_node->ss.ps.instrument || fc_pcxt->nworkers == 0)
		return;

	fc_size = mul_size(fc_pcxt->nworkers, sizeof(MemoizeInstrumentation));
	fc_size = add_size(fc_size, offsetof(SharedMemoizeInfo, sinstrument));
	shm_toc_estimate_chunk(&fc_pcxt->estimator, fc_size);
	shm_toc_estimate_keys(&fc_pcxt->estimator, 1);
}

/* ----------------------------------------------------------------
 *		ExecMemoizeInitializeDSM
 *
 *		为备忘统计初始化 DSM 空间。
 * ----------------------------------------------------------------
 */
void ExecMemoizeInitializeDSM(MemoizeState *fc_node, ParallelContext *fc_pcxt)
{
	Size		fc_size;

	/* 如果没有工具监控或没有工作程序，则不需要此 */
	if (!fc_node->ss.ps.instrument || fc_pcxt->nworkers == 0)
		return;

	fc_size = offsetof(SharedMemoizeInfo, sinstrument)
		+ fc_pcxt->nworkers * sizeof(MemoizeInstrumentation);
	fc_node->shared_info = shm_toc_allocate(fc_pcxt->toc, fc_size);
	
/* 确保任何未填充的槽将包含零 */
	memset(fc_node->shared_info, 0, fc_size);
	fc_node->shared_info->num_workers = fc_pcxt->nworkers;
	shm_toc_insert(fc_pcxt->toc, fc_node->ss.ps.plan->plan_node_id,
				   fc_node->shared_info);
}

/* ----------------------------------------------------------------
 *		ExecMemoizeInitializeWorker
 *
 *		将工作线程附加到备忘统计的 DSM 空间。
 * ----------------------------------------------------------------
 */
void ExecMemoizeInitializeWorker(MemoizeState *fc_node, ParallelWorkerContext *fc_pwcxt)
{
	fc_node->shared_info =
		shm_toc_lookup(fc_pwcxt->toc, fc_node->ss.ps.plan->plan_node_id, true);
}

/* ----------------------------------------------------------------
 *		ExecMemoizeRetrieveInstrumentation
 *
 *		将备忘统计从 DSM 转移到私有内存。
 * ----------------------------------------------------------------
 */
void ExecMemoizeRetrieveInstrumentation(MemoizeState *fc_node)
{
	Size		fc_size;
	SharedMemoizeInfo *fc_si;

	if (fc_node->shared_info == NULL)
		return;

	fc_size = offsetof(SharedMemoizeInfo, sinstrument)
		+ fc_node->shared_info->num_workers * sizeof(MemoizeInstrumentation);
	fc_si = palloc(fc_size);
	memcpy(fc_si, fc_node->shared_info, fc_size);
	fc_node->shared_info = fc_si;
}
